package net.flintx.array;

import java.util.Arrays;

public class MaximumSubarray {

    public int maxSubArray(int[] nums) {
        /**
        * maxSubArray
        *
        * @Description:
        *  Find the contiguous subarray within an array
        *  (containing at least one number) which has the largest sum.
        * @Example:
        *  Input: [-2,1,-3,4,-1,2,1,-5,4]
        *  Output: the contiguous subarray [4,-1,2,1] has the largest sum = 6
        * @Params: [nums]
        * @Return: int
        * @Date: 2018/1/4
        */

        int mid = nums.length >> 1;
        if (nums.length == 1) {
            return nums[0];
        } else {
            int leftSum = nums[mid], leftMaxSum = nums[mid], rightSum = 0, rightMaxSum = 0;
            for (int i = mid - 1; i >= 0; i--) {
                leftSum += nums[i];
                leftMaxSum = Math.max(leftMaxSum, leftSum);
            }
            for (int i = mid + 1; i < nums.length; i++) {
                rightSum += nums[i];
                rightMaxSum = Math.max(rightMaxSum, rightSum);
            }
            return Math.max(
                    Math.max(
                        maxSubArray(Arrays.copyOfRange(nums,0, mid)),
                        maxSubArray(Arrays.copyOfRange(nums, mid, nums.length))),
                    leftMaxSum + rightMaxSum);
        }
    }

    private int betterMethod(int[] nums) {
        int maxSum = nums[0];
        int maxEndingHere = maxSum;
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(maxEndingHere, 0) + nums[i];
            maxSum = Math.max(maxSum, maxEndingHere);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new MaximumSubarray().maxSubArray(nums));
        System.out.println(new MaximumSubarray().betterMethod(nums));
    }
}
